# -*- coding = utf-8 -*-
# @Time : 2021/11/29 16:49
# @Author : chenxingjia
# @File : 01背包.py


# 经典01背包问题
def bag01_0(weights, values, bag_weight):
    weights = [0] + weights
    values = [0] + values
    n = len(weights)
    dp = [[0 for _ in range(bag_weight+1)] for _ in range(n)]

    for i in range(1, n):
        for w in range(1, bag_weight+1):

            if weights[i] <= w:
                dp[i][w] = max(dp[i-1][w-weights[i]]+values[i], dp[i-1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp


def bag01_1(weights, values, bag_weight):
    n = len(weights)
    dp = [[0 for _ in range(bag_weight+1)] for _ in range(n)]

    for i in range(n):
        for w in range(1, bag_weight+1):

            if weights[i] <= w:
                dp[i][w] = max(dp[i-1][w-weights[i]]+values[i], dp[i-1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp


# 经典01背包问题优化
def bag01_2(weights, values, bag_weight):
    n = len(weights)
    dp = [0 for _ in range(bag_weight+1)]
    for i in range(n):
        for j in range(bag_weight, weights[i]-1, -1):
            dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
        print(dp)
    return dp


def main():
    wights = [2, 2, 3, 1, 5, 2]
    values = [2, 3, 1, 5, 4, 3]
    bag_weight = 10
    res = bag01_2(wights, values, bag_weight)
    print(res)
    print(res[-1])


if __name__ == '__main__':
    main()

